#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char ElemType;

typedef struct TreeNode
{
    ElemType data;
    struct TreeNode *lChild;
    struct TreeNode *rChild;
} TreeNode, *BitTree;

typedef struct QNode
{
    void *data;
    struct QNode *next;
} QNode;

typedef struct Queue
{
    QNode *front;
    QNode *rear;
} Queue;

typedef struct SNode
{
    void *data;
    struct SNode *Next;
} SNode, Stack;

void InitQueue(Queue &Q)
{
    Q.front = Q.rear = (QNode *)malloc(sizeof(QNode));
    Q.front->next = NULL;
}

bool EmptyQueue(Queue Q)
{
    return Q.front == Q.rear;
}

void EnQueue(Queue &Q, void *e)
{
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node->data = e;
    node->next = Q.rear->next;
    Q.rear->next = node;
    Q.rear = node;
}

void *DeQueue(Queue &Q)
{
    if (EmptyQueue(Q))
    {
        return NULL;
    }
    QNode *node = Q.front->next;
    void *data = node->data;
    Q.front->next = node->next;
    free(node);
    if (Q.front->next == NULL)
    {
        Q.rear = Q.front;
    }
    return data;
}

BitTree BuildTree(ElemType *elem, int len)
{
    if (len == 0)
    {
        return NULL;
    }
    BitTree tree = (TreeNode *)malloc(sizeof(TreeNode));
    tree->data = elem[0];
    tree->lChild = NULL;
    tree->rChild = NULL;
    TreeNode *curNode = tree;
    Queue queue;
    InitQueue(queue);
    for (int i = 1; i < len; i++)
    {
        TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
        node->data = elem[i];
        node->lChild = NULL;
        node->rChild = NULL;
        EnQueue(queue, node);
        if (curNode->lChild && curNode->rChild)
        {
            curNode = (TreeNode *)DeQueue(queue);
        }
        if (!curNode->lChild)
        {
            curNode->lChild = node;
        }
        else
        {
            curNode->rChild = node;
        }
    }
    return tree;
}

void PreOrderTree(BitTree tree)
{
    if (tree)
    {
        printf("%3c", tree->data);
        PreOrderTree(tree->lChild);
        PreOrderTree(tree->rChild);
    }
}

void MidOrderTree(BitTree tree)
{
    if (tree)
    {
        PreOrderTree(tree->lChild);
        printf("%3c", tree->data);
        PreOrderTree(tree->rChild);
    }
}

void PostOrderTree(BitTree tree)
{
    if (tree)
    {
        PreOrderTree(tree->lChild);
        PreOrderTree(tree->rChild);
        printf("%3c", tree->data);
    }
}

void BFS(BitTree tree)
{
    Queue queue;
    InitQueue(queue);
    EnQueue(queue, tree);
    TreeNode *curNode;
    while (!EmptyQueue(queue))
    {
        curNode = (TreeNode *)DeQueue(queue);
        printf("%3c", curNode->data);
        if (curNode->lChild)
        {
            EnQueue(queue, curNode->lChild);
        }
        if (curNode->rChild)
        {
            EnQueue(queue, curNode->rChild);
        }
    }
}

void DFS(BitTree tree)
{
    if (tree)
    {
        printf("%3c", tree->data);
        DFS(tree->lChild);
        DFS(tree->rChild);
    }
}

int main()
{
    ElemType ch[] = "abcdefghijklmno";
    BitTree tree = BuildTree(ch, 15);
    printf("\n--------------PreOrderTree-------------------\n");
    PreOrderTree(tree);
    printf("\n");
    // PreOrderTreeV2(tree);
    // printf("\n");
    // PreOrderTree2(tree);
    printf("\n-------------MidOrderTree--------------------\n");
    MidOrderTree(tree);
    printf("\n");
    // MidOrderTree2(tree);
    printf("\n-------------PostOrderTree--------------------\n");
    PostOrderTree(tree);
    // PostOrderTreeV2(tree);
    printf("\n");
    printf("\n-------------BFSOrderTree--------------------\n");
    BFS(tree);
    printf("\n");
    printf("\n-------------DFSOrderTree--------------------\n");
    DFS(tree);
    printf("\n");

    return 0;
}
